class Solution:
    def permuteUnique(self, nums):
        if not nums:
            return []
        # result 用来存放结果
        result=[]
        used=[0]*len(nums)
        def backtracking(nums,used,path):
            # 终止条件
            if len(path)==len(nums):
                result.append(path[:])
                return
            # 递归处理回溯问题
            for i in range(0,len(nums)):
                if not used[i]:
                    if i>0 and nums[i]==nums[i-1] and used[i-1]==1:
                        continue
                    used[i]=1
                    path.append(nums[i])
                    backtracking(nums,used,path)
                    path.pop()
                    used[i]=0
        # 记得给nums排序
        backtracking(sorted(nums),used,[])
        return result